A computational method utilizing divide-and-conquer and incremental computation was proposed to calculate the structure of attribute granule of an inseparable information system. Firstly, the rule that how the structure of attribute granule of an information system changed when new Functional Dependency (FD) was added to the functional dependency set of an information system was studied and the increment theorem of information system structure was proved. Secondly, by removing a part of the functional dependency, an inseparable information system could become a separable information system and the structure of the separable information system was calculated by using decomposition theorem. Thirdly, the removed functional dependency was added to the separable information system and the structure of the original information system was calculated by using increment theorem. Lastly, the algorithm to calculate the structure of attribute granule of inseparable information system was given and its complexity was analyzed. The complexity of the direct calculation of the structure of attribute granule of information system was O(n×m×2n), and the proposed method could reduce the complexity to below O(n×k×2n)(k<m), and when k=1,2, the complexity could be reduced to O(n1×m1×2n1)+O(n2×m2×2n2)(n=n1+n2,m=m1+m2). The theoretical analysis and practical calculation demonstrate that the proposed method can effectively reduce the computational complexity of the structure of attribute granule of an inseparable information system.
Based on functional dependency over the attributes, the concept of attribute information granule of information system was proposed, and a method to calculate the structure of attribute granule of separable information system was given. Firstly, the separability of information system was defined, and it was proved that if an information system is separable, the structure of attribute granule of the system can be decomposed into the Cartesian product of the structures of attribute granules of its sub-systems. Secondly, the method to judge the separability of an information system and the decomposition algorithm of information system were given. Lastly, the complexity of the proposed method was analyzed. And the analysis result demonstrates that the complexity of the direct calculation of the structure of attribute granule of information system is O(2n), and the proposed method can reduce it to O(2n1+2n2+…+2nk) where n=n1+n2+…+nk. The theoretical analysis and example show that the method is feasible.
Concerning the problem of lacking completeness and accuracy in the individuals inference information and scientificity in the overall integration results, which exists in the process of inferring Conditional Probability Table (CPT) in Bayesian network according to expert knowledge, this paper presented a method based on the Dempster-Shafer/Analytic Hierarchy Process (DS/AHP) to derive optimal conditional probability from the expert inference information. Firstly, the inferred information extraction mechanism was proposed to make judgment objects more intuitive and judgment modes more perfect by introducing the knowledge matrix of the DS/AHP method. Then, the construction process of Bayesian network was proposed following an inference sequence of "anterior to later". Finally, the traditional method and the presented method were applied to infer the missing conditional probability table in the same Bayesian network. The numerical comparison analyses show that the calculation efficiency can be improved and the accumulative total deviation can be decreased by 41% through the proposed method. Meanwhile, the proposed method is illustrated to be scientific, applicable and feasible.